package com.algorithm.learning.base.图;

/**
 * @program: algorithm-learning
 * @description: 图的生成器
 * 因为我们知道，图的结构，可能是多样的，这里的Graph仅仅是其中一种结构，在笔试和面试中可能会出现很多其他类型的结构，比如领接表，领接矩阵
 *
 * 但是图的难点就是在于结构的多样化，所以我们抽象出来一种比较通用，可以解决大部分问题的结构:Graph。
 *
 * 所以当我们遇到图的有关结构时，不管什么结构，可以先尝试，转换为熟悉的结构Graph，然后再利用Graph再解决问题。
 * 这就是GraphGenerator类的用途
 * @author: YuKai Fan
 * @create: 2024/8/29 21:10
 **/
public class GraphGenerator {

    /**
     * matrix是一个n * n 的矩阵(这个矩阵一定是正方形的)，它表达的意思其实是一个领接表
     *
     * [[weight, from, to], [weight, from, to], [weight, from, to]]
     *
     * 我们将这个领接表转为一个Graph结构
     * @param matrix
     * @return
     */
    public static Graph createGraph(int[][] matrix) {
        Graph graph = new Graph();
        for (int i = 0; i < matrix.length; i++) {
            int weight = matrix[i][0];
            int from = matrix[i][1];
            int to = matrix[i][2];

            // 构建from的点
            if (!graph.nodes.containsKey(from)) {
                graph.nodes.put(from, new Node(from));
            }
            // 构建to的点
            if (!graph.nodes.containsKey(to)) {
                graph.nodes.put(to, new Node(to));
            }
            Node fromNode = graph.nodes.get(from);
            Node toNode = graph.nodes.get(to);
            Edge edge = new Edge(weight, fromNode, toNode);
            // 添加from的直接点
            fromNode.nexts.add(toNode);
            // from的出度++
            fromNode.out++;
            // to的入度++;
            toNode.in++;
            // 添加from直接边
            fromNode.edges.add(edge);
            // 添加图的边
            graph.edges.add(edge);
        }
        return graph;
    }
}
